package com.github.kezhenxu94.playground.java.sorting;

import java.util.Arrays;

public class CountingSort {

	public int[] sort(int[] array, int upperBound) {
		int[] indices = new int[upperBound + 1];
		int[] result = new int[array.length];
		Arrays.fill(indices, 0);
		
		for (int i = 0; i < array.length; i++)
			indices[array[i]]++;
		for (int i = 1; i < indices.length; i++)
			indices[i] += indices[i - 1];
		for (int i = array.length - 1; i >= 0; i--) {
			result[indices[array[i]] - 1] = array[i];
			indices[array[i]]--;
		}
		
		return result;
	}
}
